{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Ways to Partition an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting #enumeration #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数 #枚举 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToPartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组的最多方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始且长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;。<strong>分割</strong>&nbsp;数组 <code>nums</code>&nbsp;的方案数定义为符合以下两个条件的 <code>pivot</code>&nbsp;数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pivot &lt; n</code></li>\n",
    "\t<li><code>nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>k</code>&nbsp;。你可以将&nbsp;<code>nums</code>&nbsp;中&nbsp;<strong>一个</strong>&nbsp;元素变为&nbsp;<code>k</code>&nbsp;或&nbsp;<strong>不改变</strong>&nbsp;数组。</p>\n",
    "\n",
    "<p>请你返回在 <strong>至多</strong>&nbsp;改变一个元素的前提下，<strong>最多</strong>&nbsp;有多少种方法 <strong>分割</strong>&nbsp;<code>nums</code>&nbsp;使得上述两个条件都满足。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,-1,2], k = 3\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>一个最优的方案是将 nums[0] 改为 k&nbsp;。数组变为 [<em><strong>3</strong></em>,-1,2] 。\n",
    "有一种方法分割数组：\n",
    "- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [0,0,0], k = 1\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>一个最优的方案是不改动数组。\n",
    "有两种方法分割数组：\n",
    "- pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。\n",
    "- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,<em><strong>-33</strong></em>,-20,-15,15,-16,7,19,-10,0,-13,-14] 。\n",
    "有四种方法分割数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= k, nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-ways-to-partition-an-array](https://leetcode.cn/problems/maximum-number-of-ways-to-partition-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-ways-to-partition-an-array](https://leetcode.cn/problems/maximum-number-of-ways-to-partition-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,-1,2]\\n3', '[0,0,0]\\n1', '[22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14]\\n-33']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        tot = sum(nums)\n",
    "        acc = list(accumulate(nums))[:-1]\n",
    "        cnt = Counter(acc)\n",
    "        ans = 0\n",
    "        if tot % 2 == 0:\n",
    "            ans += cnt[tot // 2]\n",
    "\n",
    "        n = len(nums)\n",
    "        left_cnt = Counter()\n",
    "        for i in range(n):\n",
    "            new_tot = tot - nums[i] + k\n",
    "            if new_tot % 2 == 0 and nums[i] != k:\n",
    "                ans = max(ans, cnt[new_tot // 2 - k + nums[i]] + left_cnt[new_tot // 2])\n",
    "            if i < n - 1:\n",
    "                left_cnt[acc[i]] += 1\n",
    "                cnt[acc[i]] -= 1\n",
    "\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "    \n",
    "#     All differences to the left of i will increase by nums[i] - k.\n",
    "# All differences starting from i will decrease by nums[i] - k.\n",
    "# Now, we go left-to-right, move differences from right to left, and track max partitions if we change the current number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        pre_had = set()   #[:i]里面有的数据\n",
    "        pre_had.add(nums[0])\n",
    "\n",
    "        suf_had = Counter(nums)\n",
    "        suf_had[nums[0]] -= 1\n",
    "\n",
    "        pre_cnt = Counter()\n",
    "        suf_cnt = Counter()\n",
    "\n",
    "        alls = sum(nums)\n",
    "        pre = nums[0]\n",
    "\n",
    "        p1 = 0\n",
    "\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            #1.啥都不变\n",
    "            if pre == alls - pre:\n",
    "                p1 += 1\n",
    "\n",
    "            #2.如果改变左边能使得相等\n",
    "            tar = 2 * pre + k - alls\n",
    "            if tar in pre_had:\n",
    "                pre_cnt[tar] += 1\n",
    "                \n",
    "\n",
    "            #3.如果改变右边能使得相等\n",
    "            tar = alls - 2 * pre + k\n",
    "            if suf_had[tar] > 0:\n",
    "                suf_cnt[tar] += 1\n",
    "\n",
    "            dp[i] += suf_cnt[nums[i]]\n",
    "            dp[i] -= pre_cnt[nums[i]]\n",
    "\n",
    "\n",
    "            pre_had.add(nums[i])\n",
    "            suf_had[nums[i]] -= 1\n",
    "\n",
    "            pre += nums[i]\n",
    "\n",
    "        ans = p1\n",
    "        for i in range(n):\n",
    "            dp[i] += pre_cnt[nums[i]]\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        pre_had = set()   #[:i]里面有的数据\n",
    "        pre_had.add(nums[0])\n",
    "\n",
    "        suf_had = Counter(nums)\n",
    "        suf_had[nums[0]] -= 1\n",
    "\n",
    "        pre_cnt = Counter()\n",
    "        suf_cnt = Counter()\n",
    "\n",
    "        alls = sum(nums)\n",
    "        pre = nums[0]\n",
    "\n",
    "        p1 = 0\n",
    "\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            #1.啥都不变\n",
    "            if pre == alls - pre:\n",
    "                p1 += 1\n",
    "\n",
    "            #2.如果改变左边能使得相等\n",
    "            tar = 2 * pre + k - alls\n",
    "            if tar in pre_had:\n",
    "                pre_cnt[tar] += 1\n",
    "                \n",
    "\n",
    "            #3.如果改变右边能使得相等\n",
    "            tar = alls - 2 * pre + k\n",
    "            if suf_had[tar] > 0:\n",
    "                suf_cnt[tar] += 1\n",
    "\n",
    "            dp[i] += suf_cnt[nums[i]]\n",
    "            dp[i] -= pre_cnt[nums[i]]\n",
    "\n",
    "\n",
    "            pre_had.add(nums[i])\n",
    "            suf_had[nums[i]] -= 1\n",
    "\n",
    "            pre += nums[i]\n",
    "\n",
    "        dp[0] = pre_cnt[nums[0]]\n",
    "        for i in range(1, n):\n",
    "            dp[i] += pre_cnt[nums[i]]\n",
    "\n",
    "        ans = p1 \n",
    "\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "        return ans\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        dis = []\n",
    "        nums_sum = 0\n",
    "        for num in nums:\n",
    "            nums_sum += num\n",
    "        for i in range(len(nums)-1):\n",
    "            nums_sum -= 2*nums[i]\n",
    "            dis.append(nums_sum)\n",
    "        r = dis.count(0)\n",
    "        # dis[i] : 从第i个元素后面分开，后面的加和比前面的和大的值\n",
    "        print(dis)\n",
    "        pre = {}\n",
    "        post = {}\n",
    "        for num in nums:\n",
    "            pre[-k+num] = 0\n",
    "            post[k-num] = 0\n",
    "        for d in dis:\n",
    "            if d in post:\n",
    "                post[d] += 1\n",
    "        # pre 和 post 现在表示前0个里需要查找的数的数量的字典 和 后len(nums)个里需要查找的数的数量的字典\n",
    "        for i in range(len(nums)):\n",
    "            r = max(r,pre[-k+nums[i]]+post[k-nums[i]])\n",
    "            if i<len(dis):\n",
    "                if dis[i] in pre:\n",
    "                    pre[dis[i]] += 1\n",
    "                if dis[i] in post:\n",
    "                    post[dis[i]] -= 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self,dis,k,index,nums):\n",
    "        # dis = copy.deepcopy(dis)\n",
    "        t = k-nums[index]\n",
    "        return dis[:index].count(-k+nums[index])+dis[index:].count(2*k-2*nums[index]-k+nums[index])\n",
    "        # for i in range(len(dis)):\n",
    "        #     if i>=index:\n",
    "        #         dis -= 2*k-2*nums[index]\n",
    "\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        # nums = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30827,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]\n",
    "        # k = 0\n",
    "        # expected = 33\n",
    "        dis = []\n",
    "        nums_sum = 0\n",
    "        for num in nums:\n",
    "            nums_sum += num\n",
    "        for i in range(len(nums)-1):\n",
    "            nums_sum -= 2*nums[i]\n",
    "            dis.append(nums_sum)\n",
    "        r = dis.count(0)\n",
    "        # dis[i] : 从第i个元素后面分开，后面的加和比前面的和大的值\n",
    "        print(dis)\n",
    "        pre = {}\n",
    "        post = {}\n",
    "        for num in nums:\n",
    "            pre[-k+num] = 0\n",
    "            post[k-num] = 0\n",
    "        for d in dis:\n",
    "            if d in post:\n",
    "                post[d] += 1\n",
    "        # pre 和 post 现在表示前0个里需要查找的数的数量的字典 和 后len(nums)个里需要查找的数的数量的字典\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            r = max(r,pre[-k+nums[i]]+post[k-nums[i]])\n",
    "            if i<len(dis):\n",
    "                if dis[i] in pre:\n",
    "                    pre[dis[i]] += 1\n",
    "                if dis[i] in post:\n",
    "                    post[dis[i]] -= 1\n",
    "            \n",
    "            # r = max(self.count(dis,k,i,nums),r)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        l=len(nums)-1\n",
    "        v=[0]*l\n",
    "        p=[0]*(l+2)\n",
    "        p[l+1]=k-nums[l]\n",
    "        e=sum(nums)\n",
    "        f=0\n",
    "        i=0\n",
    "        fsc={0}\n",
    "        tj=defaultdict(int)\n",
    "        zy=defaultdict(int)\n",
    "        for n in nums[0:-1]:\n",
    "            f=f+n\n",
    "            e=e-n\n",
    "            v[i]=f-e\n",
    "            p[i+1]=k-n\n",
    "            i+=1        \n",
    "        s=set([abs(i)  for i in v])&set([abs(i)  for i in p])\n",
    "        #print(s)\n",
    "\n",
    "        for i in range(l):          \n",
    "\n",
    "            if abs(v[i]) in s:\n",
    "                tj[v[i]]+=1\n",
    "            if -v[i] in fsc:\n",
    "                zy[-v[i]]+=1\n",
    "            elif v[i]==-p[i+1]:\n",
    "                zy[-v[i]]+=1\n",
    "                fsc.add(-v[i])  \n",
    "            if abs(p[i+2]) in s:\n",
    "                zy[p[i+2]]=max(tj[p[i+2]],zy[p[i+2]])\n",
    "                fsc.add(p[i+2])   \n",
    "        #print(v)\n",
    "        #print(p)\n",
    "        #print(zy)\n",
    "        rs=[0]\n",
    "        if zy:\n",
    "            rs=[zy[key] for key in zy]\n",
    "        return max(rs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        l=len(nums)-1\n",
    "        v=[0]*l\n",
    "\n",
    "        p=[0]*(l+2)\n",
    "        p[l+1]=k-nums[l]\n",
    "        e=sum(nums)\n",
    "        f=0\n",
    "        i=0\n",
    "        fsc={0}\n",
    "        tj=defaultdict(int)\n",
    "        zy=defaultdict(int)\n",
    "        for n in nums[0:-1]:\n",
    "            f=f+n\n",
    "            e=e-n\n",
    "            v[i]=f-e\n",
    "            p[i+1]=k-n\n",
    "            i+=1\n",
    "        \n",
    "        s=set([abs(i)  for i in v])&set([abs(i)  for i in p])\n",
    "        print(s)\n",
    "\n",
    "        for i in range(l):\n",
    "            \n",
    "\n",
    "            if abs(v[i]) in s:\n",
    "                tj[v[i]]+=1\n",
    "            if -v[i] in fsc:\n",
    "                zy[-v[i]]+=1\n",
    "            elif v[i]==-p[i+1]:\n",
    "                zy[-v[i]]+=1\n",
    "                fsc.add(-v[i])  \n",
    "            if abs(p[i+2]) in s:\n",
    "                zy[p[i+2]]=max(tj[p[i+2]],zy[p[i+2]])\n",
    "                fsc.add(p[i+2])   \n",
    "\n",
    "\n",
    "        print(v)\n",
    "        print(p)\n",
    "        print(zy)\n",
    "        rs=[0]\n",
    "        if zy:\n",
    "            rs=[zy[key] for key in zy]\n",
    "        return max(rs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        tot = sum(nums)\n",
    "        ret = 0\n",
    "        counter = Counter()\n",
    "        for i in range(n - 1):\n",
    "            f[i + 1] = f[i] + nums[i]\n",
    "            counter[f[i + 1]] += 1\n",
    "        left = Counter()\n",
    "        ret = 0 if tot & 1 else counter[tot >> 1]\n",
    "        for i in range(n):\n",
    "            if nums[i] != k:\n",
    "                diff = k - nums[i]\n",
    "                t = tot - diff\n",
    "                if t & 1 == 0:\n",
    "                    t >>= 1\n",
    "                    if i != n - 1:\n",
    "                        ret = max(ret, counter[t] + left[tot + diff >> 1])\n",
    "                    else:\n",
    "                        ret = max(ret, left[tot + diff >> 1])\n",
    "                    # print(i, tot, t, diff, counter[t], left[tot + diff >> 1], left)\n",
    "            counter[f[i + 1]] -= 1\n",
    "            left[f[i + 1]] += 1\n",
    "        \n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sum = [0] * n\n",
    "        cntR = Counter()\n",
    "        sum[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            sum[i] = sum[i - 1] + nums[i]\n",
    "            cntR[sum[i - 1]] += 1\n",
    "\n",
    "        tot = sum[n - 1]\n",
    "        ans = 0\n",
    "        if tot % 2 == 0:\n",
    "            ans = cntR[tot // 2]\n",
    "        cntL = Counter()\n",
    "\n",
    "        for i, s in enumerate(sum):\n",
    "            d = k - nums[i]\n",
    "            if (tot + d) % 2 == 0:\n",
    "                ans = max(ans, cntL[(tot + d) // 2] + cntR[(tot - d) // 2])\n",
    "            cntL[s] += 1\n",
    "            cntR[s] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        left = Counter()\n",
    "        right = Counter(pre)\n",
    "        \n",
    "        if s % 2 == 0:\n",
    "            mid = s // 2\n",
    "            ans = max(ans, sum(x == mid for x in pre[:-1]))\n",
    "        \n",
    "        for i, x in enumerate(pre):\n",
    "            v = nums[i]\n",
    "            d = k - nums[i]\n",
    "            cnt = 0\n",
    "            s += d\n",
    "            if s % 2 == 0:\n",
    "                mid = s // 2\n",
    "                right[pre[-1]] -= 1\n",
    "                cnt += left[mid]\n",
    "                cnt += right[mid-d]\n",
    "                ans = max(ans, cnt)\n",
    "                right[pre[-1]] += 1\n",
    "            s -= d\n",
    "            left[x] += 1\n",
    "            right[x] -= 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n, presum = len(nums), list(accumulate(nums))\n",
    "        left, right, total = Counter(), Counter(presum[:n - 1]), presum[-1]\n",
    "        ans = right[total / 2]\n",
    "        for i in range(n):\n",
    "            if i > 0: left[presum[i - 1]] += 1\n",
    "            if i > 0: right[presum[i - 1]] -= 1\n",
    "            leftx = (total - nums[i] + k) / 2\n",
    "            rightx = total / 2 - (k - nums[i]) / 2\n",
    "            ans = max(ans, left[leftx] + right[rightx])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        l,r = Counter(),Counter(pre[:n-1])\n",
    "        ss = pre[-1]\n",
    "        ans = r[ss/2]\n",
    "        for i in range(n):\n",
    "            if i:\n",
    "                l[pre[i-1]] += 1\n",
    "                r[pre[i-1]] -= 1\n",
    "            le = (ss - nums[i] + k) / 2\n",
    "            ri = ss / 2 - (k - nums[i]) / 2\n",
    "            ans = max(ans,l[le]+r[ri])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = [nums[0]]\n",
    "        cntR = collections.defaultdict(int)\n",
    "        for i in range(1, n):\n",
    "            pre.append(pre[-1] + nums[i])\n",
    "            cntR[pre[i - 1]] += 1\n",
    "        res = 0\n",
    "        total = pre[-1]\n",
    "        if total % 2 == 0:\n",
    "            res = cntR[total // 2]\n",
    "        \n",
    "        cntL = collections.defaultdict(int)\n",
    "\n",
    "        for i, s in enumerate(pre):\n",
    "\n",
    "            d = k - nums[i]\n",
    "            if d and ( total + d ) % 2 == 0:\n",
    "                res = max(res, cntL[(total + d) // 2] + cntR[(total - d) // 2])\n",
    "            cntL[s] += 1\n",
    "            cntR[s] -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = [nums[0]]\n",
    "        cntR = collections.defaultdict(int)\n",
    "        for i in range(1, n):\n",
    "            pre.append(pre[-1] + nums[i])\n",
    "            cntR[pre[i - 1]] += 1\n",
    "        res = 0\n",
    "        total = pre[-1]\n",
    "        if total % 2 == 0:\n",
    "            res = cntR[total // 2]\n",
    "        \n",
    "        cntL = collections.defaultdict(int)\n",
    "\n",
    "        for i, s in enumerate(pre):\n",
    "\n",
    "            d = k - nums[i]\n",
    "            if d and ( total + d ) % 2 == 0:\n",
    "                res = max(res, cntL[(total + d) // 2] + cntR[(total - d) // 2])\n",
    "            cntL[s] += 1\n",
    "            cntR[s] -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = [nums[0]]\n",
    "        cntR = collections.defaultdict(int)\n",
    "        for i in range(1, n):\n",
    "            pre.append(pre[-1] + nums[i])\n",
    "            cntR[pre[i - 1]] += 1\n",
    "        res = 0\n",
    "        total = pre[-1]\n",
    "        if total % 2 == 0:\n",
    "            res = cntR[total // 2]\n",
    "        \n",
    "        cntL = collections.defaultdict(int)\n",
    "\n",
    "        for i, s in enumerate(pre):\n",
    "\n",
    "            d = k - nums[i]\n",
    "            if d and ( total + d ) % 2 == 0:\n",
    "                res = max(res, cntL[(total + d) // 2] + cntR[(total - d) // 2])\n",
    "            cntL[s] += 1\n",
    "            cntR[s] -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sm = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        cnt_r = Counter(sm[:-1])\n",
    "        # for i in range(1, n):\n",
    "        #     sm[i] = sm[i-1] + nums[i]\n",
    "        #     cnt_r[sm[i-1]] += 1\n",
    "        tot = sm[-1]\n",
    "        if tot % 2 == 0:\n",
    "            ans = cnt_r[tot // 2]\n",
    "        cnt_l = Counter()\n",
    "        # 前缀部分和后缀部分\n",
    "        for i, c in enumerate(sm):\n",
    "            # 修改这个数字之后 前后部分的和\n",
    "            d = k - nums[i]\n",
    "            if (tot + d) % 2 == 0:\n",
    "                # 前缀的和有多少个 后缀的和有多少个\n",
    "                ans = max(ans, cnt_l[(tot + d) // 2] + cnt_r[(tot - d) // 2])\n",
    "            cnt_l[c] += 1\n",
    "            cnt_r[c] -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n, presum = len(nums), list(accumulate(nums))\n",
    "        left, right, total = defaultdict(int), Counter(presum[:n - 1]), presum[-1]\n",
    "        ans = right[total / 2]\n",
    "        for i in range(n):\n",
    "            if i > 0: left[presum[i - 1]] += 1\n",
    "            if i > 0: right[presum[i - 1]] -= 1\n",
    "            leftx = (total - nums[i] + k) / 2\n",
    "            rightx = total / 2 - (k - nums[i]) / 2\n",
    "            ans = max(ans, left[leftx] + right[rightx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和， 等于分段了。\n",
    "        n = len(nums)\n",
    "        preSum = list(accumulate(nums))\n",
    "        left = defaultdict(int)\n",
    "        right = Counter(preSum[:n-1])  # 切到[0,n-2]闭区间\n",
    "        total = preSum[-1]\n",
    "        # print(\"presum:\",preSum)\n",
    "        # print(\"right:\", right)\n",
    "        ans = right[total/2]\n",
    "        # print(ans)\n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                left[preSum[i-1]] += 1\n",
    "                right[preSum[i-1]] -= 1\n",
    "            leftx = (total-nums[i]+k) / 2\n",
    "            rightx = total/2 - (k-nums[i])/2\n",
    "            ans = max(ans, left[leftx]+right[rightx])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n,presum=len(nums),list(accumulate(nums))\n",
    "        left,right,total=defaultdict(int),Counter(presum[:n-1]),presum[-1]\n",
    "        ans=right[total/2]\n",
    "        for i in range(n):\n",
    "            if i>0:left[presum[i-1]]+=1\n",
    "            if i>0:right[presum[i-1]]-=1\n",
    "            leftx=(total-nums[i]+k)/2\n",
    "            rightx=total/2-(k-nums[i])/2\n",
    "            ans=max(ans,left[leftx]+right[rightx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        pres = list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        left , right = defaultdict(int) , Counter(pres[:-1])\n",
    "        total = sum(nums)\n",
    "        ans = right[total/2]\n",
    "        for i , num in enumerate(nums):\n",
    "            if i > 0:\n",
    "                left[pres[i-1]] += 1\n",
    "                right[pres[i-1]] -= 1\n",
    "            d = k - num\n",
    "            leftX = left[(total+d)/2]\n",
    "            rightX = right[(total-d)/2]\n",
    "            ans = max(ans,leftX + rightX)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from collections import defaultdict, Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n, presum = len(nums), list(accumulate(nums))\n",
    "        left, right, total = defaultdict(int), Counter(presum[:n - 1]), presum[-1]\n",
    "        ans = right[total / 2]\n",
    "        for i in range(n):\n",
    "            if i > 0: left[presum[i - 1]] += 1\n",
    "            if i > 0: right[presum[i - 1]] -= 1\n",
    "            leftx = (total - nums[i] + k) / 2\n",
    "            rightx = total / 2 - (k - nums[i]) / 2\n",
    "            ans = max(ans, left[leftx] + right[rightx])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\r\n",
    "        n, presum = len(nums), list(accumulate(nums))\r\n",
    "        left, right, total = defaultdict(int), Counter(presum[:n - 1]), presum[-1]\r\n",
    "        ans = right[total / 2]\r\n",
    "        for i in range(n):\r\n",
    "            if i > 0: left[presum[i - 1]] += 1\r\n",
    "            if i > 0: right[presum[i - 1]] -= 1\r\n",
    "            leftx = (total - nums[i] + k) / 2\r\n",
    "            rightx = total / 2 - (k - nums[i]) / 2\r\n",
    "            ans = max(ans, left[leftx] + right[rightx])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        pref =list(accumulate(nums))\n",
    "        right = Counter(pref[:n-1])\n",
    "        left = defaultdict(int)\n",
    "        tot = pref[-1]\n",
    "        ans = right[tot / 2]\n",
    "        # print(right)\n",
    "        # print(tot,ans)\n",
    "        for i in range(n):\n",
    "            leftx = left[(tot - nums[i] + k) / 2]\n",
    "            rightx = right[(tot - k + nums[i]) / 2]\n",
    "            \n",
    "            ans = max(ans , leftx + rightx)\n",
    "            left[pref[i]]+=1\n",
    "            right[pref[i]]-=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n, presum = len(nums), list(accumulate(nums))\n",
    "        left, right, total = defaultdict(int), Counter(presum[:n - 1]), presum[-1]\n",
    "        ans = right[total / 2]\n",
    "        for i in range(n):\n",
    "            if i > 0: left[presum[i - 1]] += 1\n",
    "            if i > 0: right[presum[i - 1]] -= 1\n",
    "            leftx = (total - nums[i] + k) / 2\n",
    "            rightx = total / 2 - (k - nums[i]) / 2\n",
    "            ans = max(ans, left[leftx] + right[rightx])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        s = sum(nums)\n",
    "        diff = {}\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for i in range(n-1):\n",
    "            t += nums[i]\n",
    "            diff[s-2*t] = diff.get(s-2*t, 0) + 1\n",
    "\n",
    "        ans = diff.get(0, 0)\n",
    "        \n",
    "        cp = {}\n",
    "        for i in range(n-1):\n",
    "            c = k - nums[i]\n",
    "            if i != 0:\n",
    "                nums[i] += nums[i-1]\n",
    "            ans = max(ans, diff.get(c, 0)+cp.get(-c, 0))\n",
    "            diff[s-2*nums[i]] -= 1\n",
    "            cp[s-2*nums[i]] = cp.get(s-2*nums[i], 0) + 1\n",
    "        ans = max(ans, cp.get(nums[-1]-k, 0))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        sums = [0]\n",
    "        n = len(nums)\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sums.append(sums[-1] + num)\n",
    "            cnt[sums[-1]] += 1\n",
    "        sums.pop(0)\n",
    "        cnt[sums[-1]] -= 1\n",
    "        total = sums[-1]\n",
    "        if total % 2 == 0:\n",
    "            ans = cnt[total // 2]\n",
    "        cntl = defaultdict(int)\n",
    "        for i, s in enumerate(sums):\n",
    "            d = k - nums[i]\n",
    "            if (d + total) % 2 == 0:\n",
    "                ans = max(ans, cntl[(total + d) // 2] + cnt[(total - d) // 2])\n",
    "            cnt[s] -= 1\n",
    "            cntl[s] += 1\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        allSum = sum(nums)\n",
    "        n = len(nums)\n",
    "        rever = Counter()\n",
    "        preSum = 0\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            preSum += nums[i]\n",
    "            rever[preSum] += 1\n",
    "\n",
    "        if allSum % 2 == 0:\n",
    "            ans = rever[allSum >> 1]\n",
    "        \n",
    "        order = Counter()\n",
    "        preSum = 0\n",
    "        for i in range(n):\n",
    "            d = k - nums[i]\n",
    "            _sum = allSum + d\n",
    "            if _sum % 2 == 0:\n",
    "                ans = max(ans, rever[(_sum - d - d) >> 1] + order[_sum >> 1])\n",
    "            preSum += nums[i]\n",
    "            order[preSum] += 1\n",
    "            rever[preSum] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        pre_had = set()   #[:i]里面有的数据\n",
    "        pre_had.add(nums[0])\n",
    "\n",
    "        suf_had = Counter(nums)\n",
    "        suf_had[nums[0]] -= 1\n",
    "\n",
    "        pre_cnt = Counter()\n",
    "        suf_cnt = Counter()\n",
    "\n",
    "        alls = sum(nums)\n",
    "        pre = nums[0]\n",
    "\n",
    "        p1 = 0   #啥都不改\n",
    "\n",
    "        dp = [0] * n   #改动第i个，能有多大种可能满足题意\n",
    "        for i in range(1, n):\n",
    "            #1.啥都不变\n",
    "            if pre == alls - pre:\n",
    "                p1 += 1\n",
    "\n",
    "            #2.如果改变左边能使得相等\n",
    "            tar = 2 * pre + k - alls\n",
    "            \n",
    "            pre_cnt[tar] += 1\n",
    "                \n",
    "\n",
    "            #3.如果改变右边能使得相等\n",
    "            tar = alls - 2 * pre + k\n",
    "            suf_cnt[tar] += 1\n",
    "\n",
    "            dp[i] += suf_cnt[nums[i]]   #nums[i]作为右边进行修改\n",
    "            dp[i] -= pre_cnt[nums[i]]   #nums[i]还不能作为左边进行修改\n",
    "\n",
    "\n",
    "            pre_had.add(nums[i])\n",
    "            suf_had[nums[i]] -= 1\n",
    "\n",
    "            pre += nums[i]\n",
    "\n",
    "        ans = p1\n",
    "        for i in range(n):\n",
    "            dp[i] += pre_cnt[nums[i]]\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        pre_cnt = Counter()\n",
    "        suf_cnt = Counter()\n",
    "\n",
    "        alls = sum(nums)\n",
    "        pre = nums[0]\n",
    "\n",
    "        ans = 0   #啥都不改\n",
    "\n",
    "        dp = [0] * n   #改动第i个，能有多大种可能满足题意\n",
    "        for i in range(1, n):\n",
    "            #1.啥都不变\n",
    "            if pre == alls - pre:\n",
    "                ans += 1\n",
    "\n",
    "            #2.如果改变左边能使得相等\n",
    "            tar = 2 * pre + k - alls\n",
    "            pre_cnt[tar] += 1\n",
    "                \n",
    "\n",
    "            #3.如果改变右边能使得相等\n",
    "            tar = alls - 2 * pre + k\n",
    "            suf_cnt[tar] += 1\n",
    "\n",
    "            dp[i] += suf_cnt[nums[i]]   #nums[i]作为右边进行修改\n",
    "            dp[i] -= pre_cnt[nums[i]]   #nums[i]还不能作为左边进行修改\n",
    "\n",
    "            pre += nums[i]\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] += pre_cnt[nums[i]]\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        pre_cnt = Counter()\n",
    "        suf_cnt = Counter()\n",
    "\n",
    "        alls = sum(nums)\n",
    "        pre = nums[0]\n",
    "\n",
    "        p1 = 0   #啥都不改\n",
    "\n",
    "        dp = [0] * n   #改动第i个，能有多大种可能满足题意\n",
    "        for i in range(1, n):\n",
    "            #1.啥都不变\n",
    "            if pre == alls - pre:\n",
    "                p1 += 1\n",
    "\n",
    "            #2.如果改变左边能使得相等\n",
    "            tar = 2 * pre + k - alls\n",
    "            pre_cnt[tar] += 1\n",
    "                \n",
    "\n",
    "            #3.如果改变右边能使得相等\n",
    "            tar = alls - 2 * pre + k\n",
    "            suf_cnt[tar] += 1\n",
    "\n",
    "            dp[i] += suf_cnt[nums[i]]   #nums[i]作为右边进行修改\n",
    "            dp[i] -= pre_cnt[nums[i]]   #nums[i]还不能作为左边进行修改\n",
    "\n",
    "            pre += nums[i]\n",
    "\n",
    "        ans = p1\n",
    "        for i in range(n):\n",
    "            dp[i] += pre_cnt[nums[i]]\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = 0\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        for i in range(1, n):\n",
    "            if pre[i] == pre[-1] - pre[i]:\n",
    "                ans += 1\n",
    "\n",
    "        # 左-右\n",
    "        cnt = [0] * n\n",
    "        post = defaultdict(int)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            b = pre[-1] - pre[i+1]\n",
    "            a = pre[i+1]\n",
    "            post[a-b] += 1\n",
    "            # 作为左边\n",
    "            cnt[i] += post[nums[i] - k]\n",
    " \n",
    "        # 右-左\n",
    "        dct = defaultdict(int)\n",
    "        for i in range(1, n):\n",
    "            b = pre[-1] - pre[i]\n",
    "            a = pre[i]\n",
    "            dct[a-b] += 1\n",
    "            # 作为右边\n",
    "            cnt[i] += dct[k - nums[i]]\n",
    "    \n",
    "        return max(ans, max(cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToPartition(self, nums: List[int], k: int) -> int:\n",
    "        acc, n = list(accumulate(nums)), len(nums)\n",
    "        d = defaultdict(list)\n",
    "        for i, j in enumerate(acc[: -1]):\n",
    "            d[j].append(i)\n",
    "        s, ans, base = acc[-1], 0, 0\n",
    "        if s % 2 == 0 and s // 2 in d:\n",
    "            ans = len(d[s // 2])\n",
    "        for i in range(n):\n",
    "            news = k - nums[i] + s \n",
    "            if news % 2: continue \n",
    "            half = news // 2\n",
    "            tar1, tar2 = d[half], d[half - k + nums[i]]\n",
    "            tmp = bisect_right(tar1, i - 1) + len(tar2) - bisect_right(tar2, i - 1)\n",
    "            ans = max(ans, tmp)\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
